package org.kfive.nova.algorithm.binarytree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * User: admin
 * Date: 16-7-16
 * Time: 下午4:55
 * To change this template use File | Settings | File Templates.
 */
public class BuildBinaryTree {

    public TreeNode build(int [] preOrder,int [] inOrder){
        TreeNode root = null;
        if(preOrder==null || inOrder == null|| preOrder.length<=0 || inOrder.length<=0){
            return  root;
        }

        root = new TreeNode();
        //先序遍历第一个值为根节点的值
        int rootValue = preOrder[0];
        root.setValue(rootValue);
        //在中序遍历中查找根节点位置，从而确定左子树和右子树
        int rootIndex = 0;
        for (int v = 0;v<inOrder.length;v++){
            if(rootValue==inOrder[v]){
                rootIndex = v;
                break;
            }
        }

        //构造左子树访问序列
        int [] leftPreOrder = Arrays.copyOfRange(preOrder,1,rootIndex+1);
        int [] leftInOrder = Arrays.copyOfRange(inOrder,0,rootIndex+1);
        root.setLeftTree(build(leftPreOrder,leftInOrder));

        //构造右子树访问序列
        int [] rightPreOrder = Arrays.copyOfRange(preOrder,rootIndex+1,preOrder.length);
        int [] rightInOrder = Arrays.copyOfRange(inOrder,rootIndex+1,inOrder.length);
        root.setRightTree(build(rightPreOrder,rightInOrder));
        return root;
    }

    /**
     * 递归先序遍历
     * @param root
     * @return
     */
    public String preOrder(TreeNode root){

        StringBuffer sb = new StringBuffer();
        if(root==null){
            return "";
        }

        sb.append(" "+ root.getValue());
        sb.append(" "+preOrder(root.getLeftTree()));
        sb.append(" "+preOrder(root.getRightTree()));

        return sb.toString();
    }

    /**
     * 递归中序遍历
     * @param root
     * @return
     */
    public String inOrder(TreeNode root){
        StringBuffer sb = new StringBuffer();
        if(root==null){
            return "";
        }

        sb.append(" "+inOrder(root.getLeftTree()));
        sb.append(" "+root.getValue());
        sb.append("" +inOrder(root.getRightTree()));
        return sb.toString();
    }

    /**
     * 递归后序遍历
     * @param root
     * @return
     */
    public String postOrder(TreeNode root){

        StringBuffer sb = new StringBuffer();
        if(root==null){
            return "";
        }

        sb.append(" "+postOrder(root.getLeftTree()));
        sb.append(" "+postOrder(root.getRightTree()));
        sb.append(" "+root.getValue());
        return sb.toString();
    }

    /**
     * 递归计算树的高度
     * @param root
     * @return
     */
    public int calDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftSubTreeDepth = calDepth(root.getLeftTree());
        int rightSubTreeDepth = calDepth(root.getRightTree());
        return Math.max(leftSubTreeDepth,rightSubTreeDepth)+1;
    }

    /**
     * 递归计算节点数
     * @param root
     * @return
     */
    public int calNodeNum(TreeNode root){
        if(root==null){
            return 0;
        }

        int leftSubTreeDepth = calDepth(root.getLeftTree());
        int rightSubTreeDepth = calDepth(root.getRightTree());
        return leftSubTreeDepth+rightSubTreeDepth+1;
    }

    /**
     * 广度优先遍历
     * @param root
     * @return
     */
    public String breadthFirstView(TreeNode root){
        StringBuffer sb = new StringBuffer();
        if(root==null){
            return "";
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();

            sb.append(node.getValue()+" ");

            if(node.getLeftTree()!=null){
                queue.offer(node.getLeftTree());
            }
            if(node.getRightTree()!=null){
                queue.offer(node.getRightTree());
            }

        }
        return sb.toString();
    }

    /**
     * 深度优先遍历
     * @param root
     * @return
     */
    public String deepFirstView(TreeNode root){
        StringBuffer sb = new StringBuffer();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root==null){
            return "";
        }
        stack.push(root);
        while (!stack.empty()){

            TreeNode node = stack.pop();
            sb.append(node.getValue()+" ");
            if(node.getRightTree()!=null){
                stack.push(node.getRightTree());
            }
            if(node.getLeftTree()!=null){
                stack.push(node.getLeftTree());
            }
        }
        return sb.toString();
    }
    /**
     * 递归实现二叉树镜像
     * @param root
     * @return
     */
    public TreeNode mirror(TreeNode root){
        if(root==null){
            return null;
        }

        TreeNode leftSubTree = mirror(root.getLeftTree());
        TreeNode rightSubTree = mirror(root.getRightTree());

        root.setLeftTree(rightSubTree);
        root.setRightTree(leftSubTree);
        return root;
    }

    /**
     * 递归计算第K层结点数
     * @param root
     * @param k
     * @return
     */
    public int kNumLayer(TreeNode root,int k){
        if(root==null||k<1){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int leftnum = kNumLayer(root.getLeftTree(),k-1);
        int rightnum = kNumLayer(root.getRightTree(),k-1);
        return leftnum+rightnum;
    }

    /**
     * 计算二叉树叶子节点个数
     * @param root
     * @return
     */
    public int GetLeafNum(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.getLeftTree()==null&&root.getRightTree()==null){
            return 1;
        }
        int leftLeafNum = GetLeafNum(root.getLeftTree());
        int rightleafNum = GetLeafNum(root.getRightTree());
        return leftLeafNum+rightleafNum;
    }


    /**
     * 递归判断两颗二叉树结构是否相同
     * 不判断value是否相同
     * @param root1
     * @param root2
     * @return
     */
    public boolean IsSameStructure(TreeNode root1,TreeNode root2){
        if(root1==null && root2==null){
            return true;
        }
        if(root1 ==null || root2==null){
            return false;
        }
        boolean leftIsSame = IsSameStructure(root1.getLeftTree(),root2.getLeftTree());
        boolean rightIsSame = IsSameStructure(root1.getRightTree(),root2.getRightTree());
        return leftIsSame&&rightIsSame;
    }

    /**
     * 是否完全二叉树
     * @param root
     * @return
     */
    public boolean IsCompleteBinaryTree(TreeNode root){
        if(root==null){
            return false;
        }

        boolean mark = false;
        boolean result = true;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(mark){
                if(node.getLeftTree()!=null || node.getRightTree()!=null){
                    result = false;
                    break;
                }
            }else {
                if(node.getLeftTree()!=null && node.getRightTree()!=null){
                    queue.offer(node.getLeftTree());
                    queue.offer(node.getRightTree());
                }else if(node.getLeftTree()!=null && node.getRightTree()==null){
                    queue.offer(node.getLeftTree());
                    mark = true;
                }else if(node.getLeftTree()==null && node.getRightTree()!=null){
                    result = false;
                    break;
                }else {
                    mark = true;
                }

            }

        }
        return result;
    }

}
